package bTree.LeetCode;

import java.util.Stack;

public class 最大矩形 {
    public int maximalRectangle(char[][] matrix) {
        //化成柱形，套用84题
        int row = matrix.length;
        int line = matrix[0].length;
        //特殊情况判断
        if (row==1&&line==1){
            return matrix[0][0]=='1'?1:0;
        }
        int [][]dp=new int[row][line];
        for (int i=0;i<line;i++){
            if (matrix[0][i]=='1'){
                dp[0][i]=1;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j=0;j<line;j++){
                if (matrix[i][j]=='1'){
                    dp[i][j]=dp[i-1][j]+1;
                }
            }
        }
        int result=0;
        for (int i = 0; i <row; i++) {
            int[] ints = dp[i];
            result=Math.max(result, largestRectangleArea(ints));
        }
        return result;
    }
    public int largestRectangleArea(int[] heights) {
        int largestRectangleArea=0;
        //末尾加0解决升序情况
        //开头加0解决第一个元素
        int[] newHeights = new int[heights.length + 2];
        newHeights[0]=0;
        newHeights[newHeights.length-1]=0;
        for (int i = 0; i < heights.length; i++) {
            newHeights[i+1]=heights[i];
        }
        //用栈记录下标
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        for (int i=1;i<newHeights.length;i++){
            if (newHeights[i]>=newHeights[stack.peek()]){
                stack.push(i);
            }else {
                while (newHeights[i]<newHeights[stack.peek()]){
                    Integer mid = stack.pop();
                    Integer left = stack.peek();
                    int right = i;
                    Integer hight = newHeights[mid];
                    int width = right - left - 1;
                    largestRectangleArea=Math.max(largestRectangleArea,hight*width );
                }
                stack.push(i);
            }
        }
        return largestRectangleArea;
    }
}

